The spread of the Internet has increased an opportunity for performing communication that needs reliability and confidentiality. The reliability means integrity of data, and the integrity of the data means that the data is not falsified during transmission. The falsification includes a data error caused by noise. The integrity is secured by using an encryption technique.
The data error may be detected by a technique using an error detection code such as a check sum. This technique is the one whereby message data is encoded into longer data to detect a data error using redundancy of the longer data. This technique has, however, a weak resistance to intentional and sophisticated falsification by a third party.
A message authentication technique is employed against intentional falsification by a third party. The message authentication technique is a generic name for techniques for detecting falsification by adding a message authentication code (MAC) to message data.
In order not to falsify data being transmitted, a situation is necessary where only a limited person can generate a valid MAC. In order to achieve that purpose, it is necessary for a transmitter and a receiver to share a common key and a MAC generating function in secret.
The transmitter inputs message data and the common key into the MAC generating function, and transmits a packet including the message data and a MAC. The receiver similarly generates a MAC using the message data and the common key and verifies whether the MAC generated is the same as the MAC received. If there is no falsification, both of the MACs are the same. If the both of the MACs are not the same, it is determined that the message data has been falsified, the MAC has been falsified, or both of the message data and the MAC have been falsified, so that the packet is discarded.
The message authentication technique is a technique different from a technique for data concealment, and cannot be used for privacy protection. When message data is desired to be concealed, the message data is encrypted, and the message authentication technique is applied to the message data encrypted. This may achieve both of detection of falsification and the data concealment.
Non-patent Literature 1 discloses an HMAC that is one of typical message authentication technologies. The HMAC is an abbreviated name for a Hash-based Message Authentication Code.
In the HMAC, hash algorithms such as SHA-1 and MD5 are used for a core portion of an operation of generating a MAC, and the hash algorithms are respectively referred to as HMAC-SHA1 and HMAC-MD5.
In the HMAC, the hash algorithm may be treated as a black box. Thus, the hash algorithm satisfying a specific condition may be used. Security of the HMAC depends on security of the hash algorithm to be used.
The security of the HMAC is resistance to spoofing. The spoofing is to counterfeit a set of a message and a MAC by a third party not having a common key. Specifically, the spoofing is an action of counterfeiting the set of the message and the MAC being different from a valid set of a message and a MAC, based on the valid set of the message and the MAC, thereby passing MAC verification by a receiver.
In the HMAC, by reducing the size of a MAC generated, it is possible to shorten the MAC to be added.
To take an example, it is possible to use, as the MAC to be added, high-order 128 bits of a 256-bit MAC to be generated when HMAC-SHA256 is used.
However, when the MAC to be added is shortened, the security of the HMAC is reduced.
Recently, a system and a service referred to as M2M are spreading. The M2M is an abbreviated name for Machine to Machine.
This system and service is provided by a network configured by using a lot of devices with limited computational resources. Then, each of the devices autonomously operates without intervention of human control. The device with the limited computational resources is a sensor node, an RFID tag, or the like. RFID is an abbreviated name for a Radio Frequency IDentifier.
When the message data has a large size, the message data is divided into a plurality of data blocks and the data blocks are communicated using a plurality of packets in order to inhibit occupancy of a network band and reduce retransmission cost for partial damage of the message data.
In this case, the MAC generated by the message data as a whole can be given to a final one of the packets, for transmission. The receiver, however, cannot verify reliability of each packet until he receives the final packet.
On contrast therewith, Patent Literature 1 discloses a technique of generating a MAC for each divided data and transmitting a packet including the divided data and the MAC.
However, when the MAC is added to each divided data in narrow-band communication, the size of the divided data may exceed an upper band limit. Thus, when the MAC has a fixed length, the size of the divided data needs to be reduced. As a result, the number of packets increases, and it therefore takes time to transmit all the packets. Then, a large load is imposed on a path for the communication.
Patent Literature 2 discloses a technique of reducing a payload by providing a MAC function to an error detection code included in a digital information signal.